95. 不同的二叉搜索树 II

const { map, mapKeys } = require("lodash");

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function(n) {
  const map = new Map();

  function build(start, end) {
    let res = [];

    if (start > end) {
      res.push(null);
      return res;
    }
    let memoryKey = `${start}_${end}`;
    if (map.has(memoryKey)) return map.get(memoryKey);
    for (let i = start; i <= end; i++) {
      const leftNode = build(start, i - 1);
      const righttNode = build(i + 1, end);
      for (let x = 0; x < leftNode.length; x++) {
        for (let y = 0; y < righttNode.length; y++) {
          res.push(new TreeNode(i, leftNode[x], righttNode[y]));
        }
      }

      map.set(memoryKey, res);
    }

    return res;
  }

  return build(1, n);
};

console.log(generateTrees(1));
console.log(JSON.stringify(generateTrees(3)));